package main

import "fmt"

type BinaryTreeNode struct {
	val   int
	left  *BinaryTreeNode
	right *BinaryTreeNode
}

//插入节点(二叉排序树)
func Insert(root *BinaryTreeNode, val int) *BinaryTreeNode {
	if root == nil {
		root = new(BinaryTreeNode)
		root.val = val
		return root
	}
	if val < root.val {
		root.left = Insert(root.left, val)
	} else { //包括等于
		root.right = Insert(root.right, val)
	}
	return root
}

//中序遍历
func inOrder(root *BinaryTreeNode) {
	if root != nil {
		inOrder(root.left)
		fmt.Printf("%d", root.val)
		inOrder(root.right)
	}
}

func main() {
	lst := []int{3, 4, 1, 2, 5, 4, 6}
	var tree *BinaryTreeNode
	for _, val := range lst {
		tree = Insert(tree, val)
	}

	inOrder(tree) //因为生成二叉排序树，遍历结果为一个升序

}
